package com.yx.study.leet.questionList.questionTwo;

import com.yx.study.leet.utils.ListNode;
import org.junit.Test;

/**
 * 61. 旋转链表
 * https://leetcode.cn/problems/rotate-list/description/
 */
public class Solution61 {
    public ListNode rotateRight(ListNode head, int k) {
        /**
         * 思路: 首尾相连转换为循环链表,在原链表倒数第k个结点处断开
         * */
        if (head == null || k == 0) return head;
        // 先将链表成环，并记录链表的长度
        // tmp 会记录住原链表最后一位节点
        int tot = 0;
        ListNode tmp = head;
        while (tmp.next != null && ++tot > 0) tmp = tmp.next;
        tot++;
        k %= tot; // 向后移动位数为listNode大小,移动后还是原链表
        if (k == 0) return head;
        // 正式成环
        tmp.next = head;
        // 从原链表 head 出发，走 tot - k - 1 步，找到「新尾结点」进行断开，并将其下一个节点作为新节点返回
        k = tot - k - 1;
        while (k-- > 0) head = head.next;
        ListNode nHead = head.next;
        head.next = null; // 断开循环链表
        return nHead;
    }

    @Test
    public void test() {
        ListNode node = new ListNode(1, 2, 3, 4, 5);
        System.out.println(rotateRight(node, 2).toString());
    }
}
